﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace DataStructure
{
    public class Sorting
    {

        #region insertion sorting
        // straight insertion sort
        public static void InsertSort<T>(List<T> list)
        {


        }
        // binary insert sort
        public static void BinaryInsertSort<T>(List<T> list)
        {


        }

        // 2-insertion sort
        public static void TwoWorkingInsertSort<T>(List<T> list)
        {


        }

        // table insertion sort
        public static void TableInsertSort<T>(List<T> list)
        {


        }
        #endregion

        #region shell sorting
        public static void ShellInsert<T>(List<T> list, int dk)
        {


        }

        public static void TableInsertSort<T>(List<T> list, int[] dlta, int t)
        {


        }
        #endregion

        #region BubbleSort
        public static void BubbleSort<T>(List<T> list)
        {


        }

        public void BubbleSort(List<int> arr)
        {
            int temp;

            for (int outer = arr.Count; outer >= 1; outer--)
            {
                for (int inner = 0; inner <= outer - 1; inner++)
                    if (arr[inner] > arr[inner + 1])
                    {
                        temp = arr[inner];
                        arr[inner] = arr[inner + 1];
                        arr[inner + 1] = temp;
                    }
            }
        }

        #endregion

        #region QuickSort
        public static void QuickSort<T>(List<T> list)
        {


        }

        #endregion

        #region selection sorting
        //simple selection sorting
        public static void SelectSort<T>(List<T> list)
        {


        }

        //tree selection sorting or tournament sort
        public static void TreeSelectSort<T>(List<T> list)
        {


        }

        #endregion

        #region HeapSort
        //heap sorting
        public static void HeapSort<T>(List<T> list)
        {


        }
        #endregion

        #region Merging sorting
        //Mergingsorting
        public static void MergingSort<T>(List<T> list)
        {


        }
        #endregion

        #region Radix sorting in list
        // Radix sorting in list
        public static void RadixSort<T>(List<T> list)
        {


        }
        #endregion
    }

    public class CArray
    {
        private int[] arr;

        public int[] Arr
        {
            get { return arr; }
            set { arr = value; }
        }
        private int upper;
        private int numElements;
        public CArray()
            : this(0)
        {

        }

        public CArray(int size)
        {
            arr = new int[size];
            upper = size - 1;
            numElements = 0;
        }
        public void Insert(int item)
        {
            arr[numElements] = item;
            numElements++;
        }
        public void DisplayElements()
        {
            for (int i = 0; i <= upper; i++)
                Console.Write(arr[i] + " ");

        }
        public void Clear()
        {
            for (int i = 0; i <= upper; i++)
                arr[i] = 0;
            numElements = 0;
        }

        public void BubbleSort()
        {
            int temp;
            for (int outer = upper; outer >= 1; outer--)
            {
                for (int inner = 0; inner <= outer - 1; inner++)
                {
                    if ((int)arr[inner] > arr[inner + 1])
                    {
                        temp = arr[inner];
                        arr[inner] = arr[inner + 1];
                        arr[inner + 1] = temp;
                    }
                }
                if (displayElements)
                {
                    Console.WriteLine();
                    Console.WriteLine("{0}:", upper - outer);
                    this.DisplayElements();
                }
            }
        }

        public void SelectionSort()
        {
            int min, temp;
            for (int outer = 0; outer <= upper; outer++)
            {
                min = outer;
                for (int inner = outer + 1; inner <= upper; inner++)
                    if (arr[inner] < arr[min])
                        min = inner;
                temp = arr[outer];
                arr[outer] = arr[min];
                arr[min] = temp;
                if (displayElements)
                {
                    Console.WriteLine();
                    Console.WriteLine("{0}:", outer);
                    this.DisplayElements();
                }
            }
        }

        public void InsertionSort()
        {
            int temp;
            for (int outter = 1; outter <= upper; outter++)
            {
                temp = arr[outter];
                for (int inner = outter - 1; inner >= 0; inner--)
                {
                    if (arr[inner] > arr[inner + 1])
                    {
                        arr[inner + 1] = arr[inner];
                        arr[inner] = temp;
                    }
                }
                if (displayElements)
                {
                    Console.WriteLine();
                    Console.WriteLine("{0}:", outter - 1);
                    this.DisplayElements();
                }
            }
        }


        public void ShellSort()
        {
            int inner, temp;
            int h = 1;
            while (h <= numElements / 3)
            {
                h = h * 3 + 1;
            }

            while (h > 0)
            {
                for (int outer = h; outer <= numElements - 1; outer++)
                {
                    temp = arr[outer];
                    inner = outer;

                    while ((inner > h - 1) && arr[inner - h] >= temp)
                    {
                        arr[inner] = arr[inner - h];
                        inner -= h;
                    }
                    arr[inner] = temp;
                }

                if (displayElements)
                {
                    Console.WriteLine();
                    Console.WriteLine("the distance is {0}:", h);
                    this.DisplayElements();
                }

                h = (h - 1) / 3;
            }
        }
        public void MergeSort()
        {
            int[] tempArray = new int[numElements];
            RecMergeSort(tempArray, 0, numElements - 1);
        }

        private void RecMergeSort(int[] tempArray, int lbound, int ubound)
        {
            if (lbound == ubound)
                return;
            else
            {
                int mid = (int)(lbound + ubound) / 2;
                RecMergeSort(tempArray, lbound, mid);
                RecMergeSort(tempArray, mid + 1, ubound);
                Merge(tempArray, lbound, mid + 1, ubound);
            }
        }

        public void Merge(int[] tempArray, int lowp, int highp, int ubound)
        {
            if (displayElements)
            {
                Console.WriteLine();
                Console.WriteLine("{0}-{1}-{2}:", lowp, highp, ubound);
            }
            int lbound = lowp;
            int mid = highp - 1;
            int n = (ubound - lbound) + 1;
            int j = 0;

            while ((lowp <= mid) && (highp <= ubound))
            {
                if (arr[lowp] < arr[highp])
                {
                    tempArray[j] = arr[lowp];
                    lowp++;
                }
                else
                {
                    tempArray[j] = arr[highp];
                    highp++;
                }
                j++;
            }

            while (lowp <= mid)
            {
                tempArray[j] = arr[lowp];
                j++;
                lowp++;
            }

            while (highp <= ubound)
            {
                tempArray[j] = arr[highp];
                j++;
                highp++;
            }



            for (int i = 0; i <= n - 1; i++)
            {
                arr[lbound + i] = tempArray[i];
            }


            if (displayElements)
            {
                Console.WriteLine();
                Console.WriteLine("{0}-{1}-{2}:", lowp, highp, ubound);
                this.DisplayElements();
            }
        }
        public bool displayElements { get; set; }
        public void QuickSort()
        {
            RecQSort(0, numElements - 1);
           
        }
        public void RecQSort(int first, int last)
        {
            if ((last - first) <= 0)
                return;
            else
            {
                int pivot = arr[last];
                int part = this.Partition(first, last);
                    RecQSort(first, part - 1);
                    RecQSort(part + 1, last);
            }
        }
        /// <summary>
        /// 0. first is for the second element, and last 
        ///     is for the last element and theFirst is for the first element.
        /// 1. Increment first until it is >= split value first stops at 91 (figure a.)
        /// 2. Decrement last until <= split value
        /// 3. Swap elements at first and last
        /// 4. Increment first until > split value or > last 
        ///    Decrement last until <= split value or < first
        /// 5. last is before first (or first is after last)
        ///     so swap elements at theFirst and last
        /// 6. Repeat process .....
        /// </summary>
        /// <param name="first"></param>
        /// <param name="last"></param>
        /// <returns></returns>
        public int Partition(int first, int last)
        {
            if (first == last)
                return first;
            int pivotVal = arr[first];
            int theFirst = first;
            bool okSide;
            first++;
            do
            {
                okSide = true;
                while (okSide)
                {
                    if (arr[first] > pivotVal)
                    {
                        okSide = false;
                    }
                    else
                    {
                        first++;
                        okSide = (first <= last);
                    }
                }
                okSide = (first <= last);
                while (okSide)
                {
                    if (arr[last] <= pivotVal)
                    {
                        okSide = false;
                    }
                    else
                    {
                        last--;
                        okSide = (first < last);
                        
                    }
                }
                if (first < last)
                {
                    Swap(first, last);
                    this.DisplayElements();
                    Console.WriteLine();
                    Console.WriteLine("-----{0}-{1}", first, last);
                    
                    first++;
                    last--;
                }
               
            } while (first <= last);

            Swap(theFirst, last);
            Console.WriteLine("{0}-{1}", theFirst, last);
            Console.WriteLine("{0}-{1}", first, last);
            this.DisplayElements();
            Console.WriteLine();
            return last;
        }

        public void Swap(int item1, int item2)
        {
            int temp = arr[item1];
            arr[item1] = arr[item2];
            arr[item2] = temp;
        }
    }

}
